A. Дек

Гоша реализовал структуру данных Дек, максимальный размер которого определяется заданным числом. Методы push_back(x), push_front(x), pop_back(), pop_front() работали корректно. Но, если в деке было много элементов, программа работала очень долго. Дело в том, что не все операции выполнялись за O(1). Помогите Гоше! Напишите эффективную реализацию.

Внимание: при реализации нельзя использовать связный список.

Формат ввода<br>
В первой строке записано количество команд n — целое число, не превосходящее 5000. Во второй строке записано число m — максимальный размер дека. Он не превосходит 1000. В следующих n строках записана одна из команд:

1) push_back(value) – добавить элемент в конец дека. Если в деке уже находится максимальное число элементов, вывести «error».<br>
2) push_front(value) – добавить элемент в начало дека. Если в деке уже находится максимальное число элементов, вывести «error».<br>
3) pop_front() – вывести первый элемент дека и удалить его. Если дек был пуст, то вывести «error».<br>
4) pop_back() – вывести последний элемент дека и удалить его. Если дек был пуст, то вывести «error».<br>

Value — целое число, по модулю не превосходящее 1000.
   

Формат вывода<br>
Выведите результат выполнения каждой команды на отдельной строке. Для успешных запросов push_back(x) и push_front(x) ничего выводить не надо.

Пример 1<br>
Ввод:<br>
4<br>
4<br>
push_front 861<br>
push_front -819<br>
pop_back<br>
pop_back<br>

Вывод:<br>
861<br>
-819<br>

Пример 2<br>
Ввод:<br>
7<br>
10<br>
push_front -855<br>
push_front 720<br>
pop_back<br>
pop_back<br>
push_back 844<br>
pop_back<br>
push_back 823<br>

Вывод:<br>
-855<br>
720<br>
844<br>

Пример 3<br>
Ввод:<br>	
6<br>
6<br>
push_front -201<br>
push_back 959<br>
push_back 102<br>
push_front 20<br>
pop_front<br>
pop_back<br>

Вывод:<br>
20<br>
102<br>
